Hiệu quả của một hệ thống mật mã khóa bất đối xứng phụ thuộc vào độ khó (lý thuyết hoặc tính toán) của một vấn đề toán học nào đó chẳng hạn như bài toán phân tích ra thừa số nguyên tố. Giải các bài toán này thường mất nhiều thời gian nhưng thông thường vẫn nhanh hơn là thử lần lượt từng khóa theo kiểu duyệt toàn bộ. Vì thế, khóa dùng trong các hệ thống này cần phải dài hơn trong các hệ thống mật mã khóa đối xứng. Tại thời điểm năm 2002, độ dài 1024 bít được xem là giá trị tối thiểu cho hệ thống sử dụng thuật toán RSA.

Năm 2003, công ty RSA Security cho rằng khóa RSA 1024 bít có độ an toàn tương đương với khóa 80 bít, khóa RSA 2048 bít tương đương với khóa 112 bít và khóa RSA 3072 bít tương đương với khóa 128 bít của hệ thống mật mã khóa đối xứng. Họ cũng đánh giá rằng, khóa 1024 bít có thể bị phá vỡ trong khoảng từ 2006 tới 2010 và khóa 2048 bít sẽ an toàn tới 2030. Các khóa 3072 bít cần được sử dụng trong trường hợp thông tin cần giữ bí mật sau 2030. Các hướng dẫn về quản lý khóa của NIST cũng gợi ý rằng khóa RSA 15360 bít có độ an toàn tương đương với khóa đối xứng 256 bít.

Một dạng khác của thuật toán mật mã hóa khóa bất đối xứng, mật mã đường cong elliptic (ECC), tỏ ra an toàn với khóa ngắn hơn khá nhiều so với các thuật toán khác. Hướng dẫn của NIST cho rằng khóa của ECC chỉ cần dài gấp đôi khóa của hệ thống khóa đối xứng. Giả định này đúng trong trường hợp không có những đột phá trong việc giải các bài toán mà ECC đang sử dụng. Một văn bản mã hóa bằng ECC với khóa 109 bít đã bị phá vỡ bằng cách tấn công duyệt toàn bộ.